package com.dycong.common.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * <p>
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @see 超出时间限制
 * @author dycong
 * @date 2019/11/19 8:54
 */
public class ThreeSum_15 {

    public static void main(String[] args) {
        ThreeSum_15 twoSum_1 = new ThreeSum_15();

//        int[] nums = {-1, 0, 1, 2, -1, -4};
        int[] nums = {-1,0,1,2,-1,-4};

        System.out.println(twoSum_1.threeSum(nums, 0));
    }

    /**
     * 受到twoSum的启发，在凑齐两人以后，他们可以找主持人登记需求的第三人，而不需要在茫茫人海中去找队友。这样，我们就把问题优化成了每个人都要找其他每个人，
     * 即时间复杂度 O(n2)O(n2)，因为需要主持人记录数据，这里还有 O(n)O(n) 的空间复杂度。
     * <p>
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * 返回的是 元素
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums, int target) {

        Map<Integer, Map<String, List<Integer>>> map = new HashMap<>();
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int element_index_i = nums[i];
                int element_index_j = nums[j];
                int need = target - element_index_i - element_index_j;

                String key = i + ":" + j;
                if (map.containsKey(need)) {
                    map.get(need).put(key, Arrays.asList(element_index_i, element_index_j));
                } else {
                    Map<String, List<Integer>> ele = new HashMap<>();
                    ele.put(key, Arrays.asList(element_index_i, element_index_j));
                    map.put(need, ele);
                }
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        Set<String> retedSet = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if (map.containsKey(cur)) {
                loop:
                for (Map.Entry<String, List<Integer>> entry : map.get(cur).entrySet()) {
                    String[] indexs = entry.getKey().split(":");
                    for (String string : indexs) {
                        if (string.equals(String.valueOf(i))) {
                            continue loop;
                        }
                    }

                    List<Integer> ele = new ArrayList<>();
                    ele.add(cur);
                    ele.addAll(entry.getValue());
                    String key = ele.stream().sorted().map(String::valueOf).collect(Collectors.joining(":"));
                    if (!retedSet.contains(key)) {
                        res.add(ele);
                        retedSet.add(key);
                    }
                }
            }
        }
        return res;
    }

    /*
      //todo 仿照位图的判断理念，存储符合的三元素的值，用于一套值返回一次的问题
        Set<Integer> visited = new HashSet<>();
        List<List<Integer>> res = new ArrayList<>();

        Map<Integer, List<Integer>> map = new HashMap<>();
        //注意双重循环的边界
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int element_index_i = nums[i];
                int element_index_j = nums[j];
                int need = target - element_index_i - element_index_j;
                //todo 为什么是 element_index_j 不是 element_index_i？0不必，nums.length-1 必须要判断
                //todo 双重循环的防重问题&&不同位置的相同元素造成的结果集相同问题
                if (map.containsKey(element_index_j)) {
                    if (visited.contains(element_index_j)) {
                        continue;
                    }

                    visited.add(element_index_j);
                } else if (!map.get(need).contains(element_index_i) || !map.get(need).contains(element_index_j)) {
                    map.put(need, Arrays.asList(element_index_i, element_index_j));
                }
            }
        }
     */

    /**
     * 受到twoSum的启发，在凑齐两人以后，他们可以找主持人登记需求的第三人，而不需要在茫茫人海中去找队友。这样，我们就把问题优化成了每个人都要找其他每个人，
     * 即时间复杂度 O(n2)O(n2)，因为需要主持人记录数据，这里还有 O(n)O(n) 的空间复杂度。
     * <p>
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * 返回的是 index 位置
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> threeSum_index(int[] nums, int target) {
        Set<Integer> visited = new HashSet<>();
        List<List<Integer>> res = new ArrayList<>();

        Map<Integer, List<Integer>> map = new HashMap<>();
        //注意双重循环的边界
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int element_index_i = nums[i];
                int element_index_j = nums[j];
                int need = target - element_index_i - element_index_j;

                //todo 为什么是 element_index_j 不是 element_index_i？0不必，nums.length-1 必须要判断
                //todo 双重循环的放重问题
                if (map.containsKey(element_index_j) && !visited.contains(j)) {
                    List<Integer> ele = new ArrayList<>();
                    ele.add(j);
                    ele.addAll(map.get(element_index_j));
                    res.add(ele);
                    visited.add(j);
                } else {
                    map.put(need, Arrays.asList(i, j));
                }
            }
        }

        return res;
    }


}
